-module(board_solver).
-compile(export_all).

%% Checks a board of arbitrary size and returns whether one of the players has
%% won an X in a row game, where X can also be any number.

%% Takes a list of counts of consecutive squares and returns whether
%% one of the counts represents a win.
has_won(P, [Curr|_], Limit) when Curr >= Limit ->
    P;
has_won(P, [_Curr|Rest], Limit) ->
    has_won(P, Rest, Limit);
has_won(_, [], _) ->
    no_winner.

consecutive({_, _}, e) ->
    {e, 0}; % empties never count for nothing, that way empty can't win. 
consecutive({A, Count}, A) ->
    {A, Count + 1};
consecutive({_, _}, A) ->
    {A, 1}.

%% Calculates the consecutive number of squares for both diagonals
%% of a given square, based on existing counts of consecutive diagonals
%% from the previous row.
%% The input list defines the diagonal acc data for three squares from
%% the previous row for both directions (coming from the left, coming
%% from the right). Example (values aligned by row index):
%%
%% Diag counts for prev:   {a, 2, 1}  {a, 1, 1}, {b, 1, 2}
%% Current value:                         a
%% Resulting diag count:              {a, 3, 1}
consecutive_diagonals([{LDgP, LDgLCount, _LDgRCount}, 
		       _, 
		       {RDgP, _RDgLCount, RDgRCount}], Curr) ->
    {Curr, DgLCount} = consecutive({LDgP, LDgLCount}, Curr),
    {Curr, DgRCount} = consecutive({RDgP, RDgRCount}, Curr),
    {Curr, DgLCount, DgRCount}.

%% Computes the count of consecutives for a single square taking into 
%% account all other relevant squares seen so far (previous rows and 
%% to the left of the current row.)
square_result(HorAcc, VertAcc, DgTripleAcc, Curr, NoWinnerAcc) ->
    {
	       case Curr of 
		   e -> 
		       no_winner;
		   _ -> NoWinnerAcc
	       end,
	       consecutive(HorAcc, Curr), consecutive(VertAcc, Curr), 
	       consecutive_diagonals(DgTripleAcc, Curr)
	      }.

verify_board(Board, Limit) ->
    verify_board(Board, Limit, 
		 {{e, 0},
		  lists:map(fun(_) ->
				    {e, 0} end, Board),
		  lists:map(fun(_) ->
				    {e, 0, 0} end, Board)},
		 no_winner, cat).

%% Processes the rows of the board one at a time, it will stop as soon
%% as it finds a winner.
%% verify_row doesn't know about edges, so for the diagonals we pad the 
%% left with "out of the board" diagonal counts. The right is handled
%% by pattern matching in verify_row.
%% Originally I was appending {e, 0, 0} at the end of the diagonals as
%% well but that was probably making the algorithm O(n^2) (assuming erlang 
%% lists are just standard linked lists and have no pointer to the last 
%% element at the head)
verify_board([Row|Rest], Limit, {_HAcc, VAcc, DiagAcc}, 
	     WinnerAcc, NoWinnerAcc) ->
    {Res, NewAccs} = verify_row(
		    {e, 0}, 
		    VAcc, 
		    [{e, 0, 0}|DiagAcc], 
		    Row, 
		    Limit, WinnerAcc, NoWinnerAcc),
    case Res of
	%% This is not very readable.. It's all because of the mess 
	%% in verify_row. Basically Res is a combination of finding
	%% an actual player winner and detecting empty squares.
	no_winner ->
	    verify_board(Rest, Limit, NewAccs, no_winner, no_winner);
	cat ->
	    verify_board(Rest, Limit, NewAccs, no_winner, cat);
	_ -> Res
    end;
verify_board([], _Limit, _Accs, WinnerAcc, NoWinnerAcc) ->
    %% TODO: Refactor this, we are doing this both here and in 
    %% verify_row
    case WinnerAcc of
	no_winner ->
	    NoWinnerAcc;
	_ ->
	    WinnerAcc
    end.


%% Checks the state of a single row using the accumulators from 
%% the previous row.
verify_row(HAcc, VAccs, DAccs, List, Limit) ->
    verify_row(HAcc, VAccs, DAccs, List, Limit, no_winner, cat).

%% Here's where everything went wrong, this code is a mess. It was all very clear in 
%% my head at the start.. 
verify_row(HAcc, [VAcc|VRest], 
	    [DAccL, DAccM, DAccR|DRest], [Curr|Rest],
	   Limit, WinnerAcc, NoWinnerAcc) ->

    %% We get the state of the current square
    {NewNoWinnerAcc, {Curr, NewHCount}, {Curr, NewVCount}, {Curr, NewLDCount, NewRDCount}} = 
	square_result(HAcc, VAcc, [DAccL, DAccM, DAccR], Curr, NoWinnerAcc),

    io:format("~nSquare Result for ~p is ~p~n", [[Curr|Rest], square_result(HAcc, VAcc, [DAccL, DAccM, DAccR], Curr, NoWinnerAcc)]),

    %% ...then find out if there's a winner based on the 4 possible counts.
    NewHasWinner = 
	has_won(Curr, [NewHCount, NewVCount, NewLDCount, NewRDCount], Limit),

    %% And recurse to check the rest of the row. TODO: tail call, why am I passing in 
    %% the WinnerAcc otherwise? 
    {Winner, {RecHAcc, RecVAcc, RecDAcc}} =
	verify_row(
	  {Curr, NewHCount}, %% We just computed this and it's used immediately
	  %% But the vert. and diagonal counts we still take from the previous row
	  VRest, 
	  %% Mid and right become left and mid for the next recursion
	  [DAccM|[DAccR|DRest]],
	  Rest, 
	  Limit,     
	  %% First winner found is the winner, but we sill want to get
	  %% the counts for the rest of the row, though I'm not sure why.
	  case WinnerAcc of
	      no_winner ->
		  NewHasWinner;
	      _ -> WinnerAcc
	  end,
	  NewNoWinnerAcc
	 ),
        
    {Winner, 
     {
       RecHAcc, 
       [{Curr, NewVCount}|RecVAcc],
       [{Curr, NewLDCount, NewRDCount}|RecDAcc]
      }
    };

%% This is for the last square in the row, there's no DAccR for that one 
%% so we just make it up here with empties. 
verify_row(HAcc, VAcc, [DAccL, DAccM], List, Limit, WinnerAcc, NoWinnerAcc) ->
    verify_row(HAcc, VAcc, [DAccL, DAccM, {e, 0, 0}], List, Limit, WinnerAcc, NoWinnerAcc);

verify_row(HAcc, [], _Diags, [], _Limit, WinnerAcc, NoWinnerAcc) ->
    %% io:format("~nWinnerAcc: ~p, NoWinnerAcc: ~p~n", [WinnerAcc, NoWinnerAcc]),
    {case WinnerAcc of
	 no_winner ->
	     NoWinnerAcc;
	 _ -> WinnerAcc
     end, {HAcc, [], []}}.

%% This should do the exact same as the one in the tictactoe module (but it
%% doesn't currently, there's no draws.)
tictactoe([A, B, C, D, E, F, G, H, I]) ->
    verify_board([[A, B, C], [D, E, F], [G, H, I]], 3).

